#pragma once
#include <iostream>
#include <queue>

using namespace std;

class TreeNode
{
public:
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(char x)
	{
		val = x;
		left = nullptr;
		right = nullptr;
	}
};

class BTree
{
public:
	BTree()
	{
		root = nullptr;
	}
	
	TreeNode* _CreateTree(char* arr, int& i)
	{
		if (arr[i] == '#')
		{
			i++;
			return nullptr;
		}
		TreeNode* node = new TreeNode(arr[i]);
		node->val = arr[i];
		i++;
		node->left = _CreateTree(arr, i);
		node->right = _CreateTree(arr, i);
		return node;
	}
	void CreateTree(char* arr, int& i)
	{
		root = _CreateTree(arr, i);
	}
	void _TreePrevOrder(TreeNode* root)
	{
		if (root == nullptr) return;
		cout << root->val << " ";
		_TreePrevOrder(root->left);
		_TreePrevOrder(root->right);
	}
	void TreePrevOrder()
	{
		_TreePrevOrder(root);
		cout << endl;
	}
	int _Size(TreeNode* root)
	{
		if (root == nullptr) return 0;
		return _Size(root->left) + _Size(root->right) + 1;
	}
	int Size()
	{
		return _Size(root);
	}
	int _LeaveSize(TreeNode* root)
	{
		if (root == nullptr) return 0;
		if (root->left == nullptr && root->right == nullptr)
		{
			return 1;
		}
		return _LeaveSize(root->left) + _LeaveSize(root->right);
	}
	int LeaveSize()
	{
		return _LeaveSize(root);
	}
	int _Ksize(TreeNode* root, int k)
	{
		if (root == nullptr) return 0;
		if (k == 1) return 1;
		return _Ksize(root->left, k - 1) + _Ksize(root->right, k - 1);
	}
	int Ksize(int k)
	{
		return _Ksize(root, k);
	}
	
	void LevelOrder()
	{
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty())
		{
			TreeNode* r = q.front();
			if (r->left)
			{
				q.push(r->left);
			}
			if (r->right)
			{
				q.push(r->right);
			}
			cout << r->val << " ";
			q.pop();
		}
	}

	bool IsBTree()
	{
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty())
		{
			TreeNode* r = q.front();
			if (r == nullptr) break;
			q.push(r->left);
			q.push(r->right);
			q.pop();
		}
		while (!q.empty())
		{
			return false;
		}
		return true;
	}

	void Delete(TreeNode* root)
	{
		if (root == nullptr) return;
		Delete(root->left);
		Delete(root->right);
	}
	~BTree()
	{
		Delete(root);
	}
private:
	TreeNode* root;
};


